package com.example.demo.leetcode.codetop.bytedance;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 示例 2：
 *
 * 输入：nums = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：nums = [0]
 * 输出：[]
 *
 *   1 2 0 -2
 *   -》 1  （2 0 -2）
 *   -》 1 2 (0 -2)
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/2/24 16:52
 */
public class 三数之和 {

    /**
     * @Desciption:
     *  方法一 暴力递归，然后使用map排除掉重复的集合,时间复杂度高
     *
     * @param nums:
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resList = new ArrayList<>();
        Map<String,List<Integer>> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            List<Integer> set = new ArrayList<>();
            process(i,0,nums,set,map);
        }
        for(List<Integer> value : map.values()){
          resList.add(value);
        }
        return resList;
    }

    public static void process(int index, int sum, int [] nums, List<Integer> set,Map<String,List<Integer>> map){

        if(set.size() > 3 || index >=nums.length){
            return;
        }
        int res = sum+nums[index];
        set.add(nums[index]);
        if(res == 0 && set.size() == 3){
            String key = createKey(set);
            map.put(key,new ArrayList<>(set));
            set.remove(new Integer(nums[index]));
            return;
        }
        set.remove(new Integer(nums[index]));

        for(int i=index+1;i<nums.length;i++){
            set.add(nums[index]);
            process(i,sum+nums[index],nums,set,map);
            set.remove(new Integer(nums[index]));
        }

    }

    public static String createKey(List<Integer> list){
        StringBuffer sb = new StringBuffer();
        Collections.sort(list);
        for(Integer s : list){
            sb.append(s);
        }
        return sb.toString();
    }


    /**
     * @Desciption:
     *  方法二: 头尾指针
     *  (1)数组从小到大排序
     *  (2)遍历数组，取一个数，针对这个数 设置左右指针(i->L->  <-R)，相加和为sum后判断时候为0，
     *  (3)如果 sum > 0 右指针左移
     *  (4)如果 sum < 0 左指针右移
     *  (5)如果 sum == 0，左指针右移判断是否还是 == 0， 是的话 左指针右移
     *  (7)如果 sum == 0, 右指针左移判断是否还是 == 0, 是的话 右指针左移
     *  (8) sum == 0，且指针无法移动，加入集合，左指针右移，右指针左移。
     *  (9)为什么不会出现重复的？因为数组是递增的。
     * @param nums:
     */
    public static List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> resList = new ArrayList<>();
        Arrays.sort(nums);
        if(nums.length < 3){
            return resList;
        }
        for(int i = 0;i<nums.length-1;i++){
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            process(i,nums,resList);
        }
        return resList;
    }


    public static void process(int i,int [] nums,List<List<Integer>> resList){
        int L = i + 1;
        int R = nums.length-1;
        while(L < R){
            int sum = nums[L] + nums[R] + nums[i];
            if(sum > 0){
                R--;
                continue;
            }
            if(sum < 0){
                L++;
                continue;
            }
            if(sum == 0){
                while(L+1 < i && nums[L+1] + nums[R] + nums[i] == 0) L++;
                while(R-1 > i && nums[L] + nums[R-1] + nums[i] == 0) R--;
                Integer [] arr = {nums[L], nums[i], nums[R]};
                ArrayList<Integer> list = new ArrayList(Arrays.asList(arr));
                resList.add(list);
                L++;
                R--;
            }
        }

    }



    public static void main(String[] args) {
        int [] arr={-1,0,1,2,-1,-4};
        List<List<Integer>> lists = threeSum2(arr);
        for(List<Integer> list : lists){
            for(Integer integer : list){
                System.out.println(integer);
            }
        }
    }
}
